package dujiu.leetcode.greed;

import java.util.Arrays;

public class P1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 排K次序，每次都将最小的取反
        // for (int i = 0; i < k; i++) {
        //     Arrays.sort(nums);
        //     nums[0] = -nums[0];
        // }
        // int sum =0 ;
        // for (int num : nums) {
        //     sum += num;
        // }
        // return sum;

        Arrays.sort(nums);
        int i = 0;
        while (k>0 && i < nums.length && nums[i] < 0){
            nums[i] = -nums[i];
            k--;
            i++;
        }
        // 如果剩下的k为奇数，取反最小的元素
        if (k>0 && k % 2 != 0){
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
}
